Copyright ã1995 by NeXT Computer, Inc.  All Rights Reserved.

IXCursorPositioning

Adopted By:	IXBTreeCursor

Declared In:	btree/protocols.h

Protocol Description

The IXCursorPositioning protocol defines methods for locating an item in a key space.  A key space is an ordered set of all possible keys of a particular type.  An example of an integer key space is the natural ordering of integers; one key space of type char * is the lexical ordering of all ASCII strings; another key space of type char * is the case insensitive lexical ordering of all ASCII strings.  The range of a key space may be restricted by a maximum key length.

Key spaces are generally used to store values, each key being associated with exactly one value.  Consider a key space that associates string-valued keys with personnel records.  Say the key contains the last name of the employee, followed by a comma, followed by the first name.  Using an IXBTreeCursor, the record for an employee named Jane Draper could be found as follows:

IXBTreeCursor *cursor;
BOOL           found;
char          *aKey = "Draper,Jane";

/* the null terminator is included in the length by convention */
found = [cursor setKey:(void *)aKey andLength:1+strlen(aKey)];

setKey:andLength: returns YES if the cursor successfully locates a value for the given key.  The cursor will remain positioned at that key following the operation, and subsequent messages to the cursor may either access that value, or move the cursor to another position.  For example, telling the cursor to write a value in the example above would overwrite Jane Draper's record, and telling the cursor to remove the value would remove her record from the key space.  Telling the cursor to move to the next key in the key space would cause it to access a different employee's record.  The cursor is therefore like an agent in the key space; it can move about and operate on the values associated with keys.

If the setKey:andLength: in the preceding example returned NO, it would indicate that there was no record associated with the key ªDraper,Janeº; the cursor would nevertheless be positioned at that key.  This may be between two existing records, before the first record, or after the last existing record.  Subsequent messages to the cursor may cause it to slide forward to the next key with an associated record.

Sliding and Insertion

A cursor at a position with no key can't access a value there.  If the cursor is asked to access a value anyway, it has two options:  try to find a value, or indicate that it can't access one.  Where it makes sense, a cursor should try to find a value by sliding forward in the key space to the next actual key.  When this isn't possible or desirable, the cursor should indicate that it can't find or access a value, by raising the IX_NotFoundError exception.

Suppose the IXBTreeCursor above is asked to look for Anne Draper instead of Jane, and that there is no record for Anne Draper; also, there are no records whose keys would fall between Anne Draper and Jane Draper.  The IXBTreeCursor will position itself before Jane's key and return NO:

aKey = "Draper,Anne";

found = [cursor setKey:(void *)aKey andLength:1+strlen(aKey)];

In this case, found will be NO, indicating that there is no key with the value ªDraper,Anneº.  If the IXBTreeCursor is asked to read the value of either the key or the personnel record, the key will slide forward to Jane's record and return that data.  For example, on determining that there is no record with the key ªDraper,Anneº, the program could send getKey:andLength: to find out where the cursor actually landed.  In this case, the cursor will move forward to Jane Draper's record, and return the key ªDraper,Janeº, along with its length.  This lets the program know that the cursor landed before Jane's record (and incidentally finds the record the program was actually interested in).

If the IXBTreeCursor is asked to write a value at a location where there is none, the value and the key are added to the key space.  Since the cursor is where it should be for the key being added, it can simply create a key and store the record under the key.  There will then be an entry in the IXBTree for Anne Draper.  This is exactly how an insertion is performed with a cursor:  set the key position with setKey:andLength:, and if the return value is NO, a write message immediately following will insert the value provided under the key.

If the IXBTreeCursor is asked to write inside or to remove the record at a location where there is no key, there's a problem.  Since there is no record, and since writing into part of a record or removing it would change data that the programmer probably doesn't want altered (namely, the record for the next actual key), the IXBTreeCursor will indicate that there is no value to write into by raising IX_NotFoundError.

Iteration and Partial Lookup

A cursor can be explicitly told to slide forward with the setNext method, which returns YES if there is a next key and the cursor has moved there, and NO if the cursor was already at the last key and has moved past it.  By sending a setFirst message to a cursor, which positions it at the first key (if there is one), and then many setNext messages, it's possible to iterate over the entire set of keys and values stored in the key space.  The same can be done in reverse order with setLast and setPrevious.

Cursor sliding and iteration can be used together to perform partial lookups, where the goal is to find all records whose keys lie within a certain range; for example, finding all employees whose last name is Draper.  This can be done by positioning the cursor at the lowest valued key, and moving it forward until the key becomes greater than the greatest valued desired.  For example, to find all employees whose last name is Draper:

BOOL  found;
char *aKey, *lastName;
int   aLength;

/*
 * Tell the cursor to find the first record whose key starts with
 * "Draper,".  Notice the comma at the end; this is to make sure
 * the last name is matched exactly.
 */
aKey = lastName = "Draper,º;
[cursor setKey:(void *)aKey andLength:1+strlen(aKey)];

/*
 * This forces the cursor to move to a real key if it didn't hit
 * one, which is probably the case.
 */
found = [cursor getKey:&(void *)aKey andLength:&aLength];

/*
 * While the key contains the last name we're looking for,
 * keep processing.  If the range were integers from 10-100,
 * aKey would be an int *, *aKey would be set to 10 for
 * the setKey:andLength: method above, and this test
 * would be (*aKey <= 100).
 */
if (YES == found) {
  while (strncmp(aKey, lastName, strlen(lastName)) >= 0) {
      processRecordAtCursor(cursor); /* process the record  */
      found = [cursor setNext];      /* go to the next one  */
      if (found == NO) break;        /* at end of key space */
      [cursor getKey:&(void *)aKey andLength:&aLength];
  }
}

Method Types

Absolute positioning	- setKey:andLength:
- getKey:andLength:

Relative positioning	- setFirst
- setNext
- setLast
- setPrevious

Checking positioning success	- isMatch

Instance Methods

getKey:andLength:

- (BOOL)getKey:(void **)aKey andLength:(unsigned int *)aLength

Returns by reference the key defining the cursor's position in its key space, along with the key's length.

Note:  Your application should use the NXSwapBigTypeToHost() function to convert the byte-order of the retrieved key to that of the machine it's running on.

If the cursor is at a key which has a value associated with it, this method returns YES.  If the cursor is between two values or before the first one, this method advances the cursor to the key for the next value, returns that key by reference, and returns YES.  If the cursor is beyond the last key, this method returns NO, and the contents of aKey and aLength aren't set.

aKey isn't guaranteed to remain the same after subsequent messages to the cursor, since the cursor reallocate its buffer or may slide as a side effect of a message.  Your code should copy their contents if it needs to save them.  Your code should not write into aKey;  doing so will corrupt the cursor.

See also:  - setKey:andLength:, - isMatch

isMatch

- (BOOL)isMatch

Returns YES if the cursor is on a key with an associated value, NO if the cursor is between two values or past either end of the set of values.

If the cursor isn't on a key with a value, then trying to get a key or read a value can cause the cursor to move forward to the next key with a value before reading the key or value, or raise IX_ArgumentError if the cursor can't move (because it's at the end of the key space).  Any attempt to write into or remove a nonexistent value will raise IX_ArgumentError.

See also:  - setKey:andLength:, - getKey:andLength:

setFirst

- (BOOL)setFirst

If there is at least one value associated with a key, this method positions the cursor at the first element's key and returns YES.  Otherwise it returns NO, and any attempt to remove or read a value at the cursor's position will raise IX_ArgumentError.

See also:  - setNext, - setLast, - setPrevious

setKey:andLength:

- (BOOL)setKey:(void *)aKey andLength:(unsigned int)aLength

Sets the current position of the cursor to that specified by aKey and aLength.

Note:  Your application should use the NXSwapHostTypeToBig() function before invoking this method, to convert the byte-order of the key to big-endian (the standard byte-order for the Indexing Kit).

If a value is associated with aKey, returns YES.  Otherwise returns NO.  If there is no value with a key before aKey, this method positions the cursor before the first value.  If there is no value with a key after aKey, this method positions the cursor beyond the last values.

If this method returns NO, then any attempt to write into or remove a value at the cursor's position will raise IX_ArgumentError, and any attempt to read a key or value will cause the cursor to move to the key for the next value before reading the key or value, or raise IX_ArgumentError if the cursor can't move (because it's at the end of the key space).

See also:  - getKey:andLength:, - isMatch

setLast

- (BOOL)setLast

If there is at least one value associated with a key, this method positions the cursor at the last element's key and returns YES.  Otherwise it returns NO, and any attempt to remove or read a value at the cursor's position will raise IX_ArgumentError.

See also:  - setPrevious, - setFirst, - setNext

setNext

- (BOOL)setNext

Sets the cursor's position to the next key with an associated value.  Returns YES if there is a next element, and NO if the cursor is already positioned at the end of the key space.  If this method returns NO, then any attempt to remove or read a value at the cursor's position will raise IX_ArgumentError.

See also:  - setFirst, - setLast, - setPrevious

setPrevious

- (BOOL)setPrevious

Sets the cursor's position to the previous key with an associated value.  Returns YES if there is a previous element, and NO if the cursor was positioned at the beginning of the key space and has moved to a position before the first key.  If this method returns NO, then any attempt to read a value will cause the cursor to move to the next key with a value, or raise IX_ArgumentError if the cursor can't move (because it's at the end of the key space).

See also:  - setLast, - setFirst, - setNext